#ifndef  __UTIL_HPP__
#define  __UTIL_HPP__
#include "asInclude.h"
#include "Grid.h"

namespace Util {
	typedef vector<vector<int > > Path;

	typedef vector<int > PathXY;
}

using namespace Util;
/**
* Backtrace according to the parent records and return the path.
* (including both start and end nodes)
* @param {Node} node End node
* @return {Array.<Array.<number>>} the path
*/
extern void backtrace(asNode *node,Path &path);

extern Path biBacktrace(asNode *nodeA, asNode *nodeB);

/**
 * Compute the length of the path.
 * @param {Array.<Array.<number>>} path The path
 * @return {number} The length of the path
 */
extern int pathLength(Path path);
/**
 * Given the start and end coordinates, return all the coordinates lying
 * on the line formed by these coordinates, based on Bresenham's algorithm.
 * http://en.wikipedia.org/wiki/Bresenham's_line_algorithm#Simplification
 * @param {number} x0 Start x coordinate
 * @param {number} y0 Start y coordinate
 * @param {number} x1 End x coordinate
 * @param {number} y1 End y coordinate
 * @return {Array.<Array.<number>>} The coordinates on the line
 */
extern Path interpolate(int x0, int y0, int x1, int y1);
/**
 * Given a compressed path, return a new path that has all the segments
 * in it interpolated.
 * @param {Array.<Array.<number>>} path The path
 * @return {Array.<Array.<number>>} expanded path
 */
extern Path expandPath(Path path);
/**
 * Smoothen the give path.
 * The original path will not be modified; a new path will be returned.
 * @param {PF.Grid} grid
 * @param {Array.<Array.<number>>} path The path
 */
extern Path smoothenPath(Grid *grid, Path &path);
/**
 * Compress a path, remove redundant nodes without altering the shape
 * The original path is not modified
 * @param {Array.<Array.<number>>} path The path
 * @return {Array.<Array.<number>>} The compressed path
 */
extern Path compressPath(Path path);
#endif //!__UTIL_HPP__
